Search Results

Documents authored by Sivadasan, Naveen

Document
DOI: 10.4230/LIPIcs.WABI.2019.7
Read Mapping on Genome Variation Graphs

Authors: Kavya Vaddadi, Rajgopal Srinivasan, and Naveen Sivadasan

Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)

Abstract
Genome variation graphs are natural candidates to represent a pangenome collection. In such graphs, common subsequences are encoded as vertices and the genomic variations are captured by introducing additional labeled vertices and directed edges. Unlike a linear reference, a reference graph allows a rich representation of the genomic diversities and avoids reference bias. We address the fundamental problem of mapping reads to genome variation graphs. We give a novel mapping algorithm V-MAP for efficient identification of small subgraph of the genome graph for optimal gapped alignment of the read. V-MAP creates space efficient index using locality sensitive minimizer signatures computed using a novel graph winnowing and graph embedding onto metric space for fast and accurate mapping. Experiments involving graph constructed from the 1000 Genomes data and using both real and simulated reads show that V-MAP is fast, memory efficient and can map short reads, as well as PacBio/Nanopore long reads with high accuracy. V-MAP performance was significantly better than the state-of-the-art, especially for long reads.
Cite as

Kavya Vaddadi, Rajgopal Srinivasan, and Naveen Sivadasan. Read Mapping on Genome Variation Graphs. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{vaddadi_et_al:LIPIcs.WABI.2019.7,
  author =	{Vaddadi, Kavya and Srinivasan, Rajgopal and Sivadasan, Naveen},
  title =	{{Read Mapping on Genome Variation Graphs}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-123-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{143},
  editor =	{Huber, Katharina T. and Gusfield, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.7},
  URN =		{urn:nbn:de:0030-drops-110375},
  doi =		{10.4230/LIPIcs.WABI.2019.7},
  annote =	{Keywords: read mapping, pangenome, genome variation graphs, locality sensitive hashing}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.365
Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion

Authors: R. B. Sandeep and Naveen Sivadasan

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
A diamond is a graph obtained by removing an edge from a complete graph on four vertices. A graph is diamond-free if it does not contain an induced diamond. The Diamond-free Edge Deletion problem asks to find whether there exist at most k edges in the input graph whose deletion results in a diamond-free graph. The problem was proved to be NP-complete and a polynomial kernel of O(k^4) vertices was found by Fellows et. al. (Discrete Optimization, 2011). In this paper, we give an improved kernel of O(k^3) vertices for Diamond-free Edge Deletion. We give an alternative proof of the NP-completeness of the problem and observe that it cannot be solved in time 2^{o(k)} * n^{O(1)}, unless the Exponential Time Hypothesis fails.
Cite as

R. B. Sandeep and Naveen Sivadasan. Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 365-376, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{sandeep_et_al:LIPIcs.IPEC.2015.365,
  author =	{Sandeep, R. B. and Sivadasan, Naveen},
  title =	{{Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{365--376},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.365},
  URN =		{urn:nbn:de:0030-drops-55976},
  doi =		{10.4230/LIPIcs.IPEC.2015.365},
  annote =	{Keywords: edge deletion problems, polynomial kernelization}
}
Document
DOI: 10.4230/DagSemProc.05031.22
Online Scheduling with Bounded Migration

Authors: Peter Sanders, Naveen Sivadasan, and Martin Skutella

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
Consider the classical online scheduling problem where jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by~$\beta$ times the size of the arriving job. Our main result is a linear time `online approximation scheme', that is, a family of online algorithms with competitive ratio~$1+\epsilon$ and constant migration factor~$\beta(\epsilon)$, for any fixed~$\epsilon>0$. This result is of particular importance if considered in the context of sensitivity analysis: While a newly arriving job may force a complete change of the entire structure of an optimal schedule, only very limited `local' changes suffice to preserve near-optimal solutions. We believe that this concept will find wide application in its own right. We also present simple deterministic online algorithms with migration factors~$\beta=2$ and~$\beta=4/3$, respectively. Their competitive ratio~$3/2$ beats the lower bound on the performance of any online algorithm in the classical setting without migration. We also present improved algorithms and similar results for closely related problems. In particular, there is a short discussion of corresponding results for the objective to maximize the minimum load of a machine. The latter problem has an application for configuring storage servers that was the original motivation for this work.
Cite as

Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online Scheduling with Bounded Migration. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{sanders_et_al:DagSemProc.05031.22,
  author =	{Sanders, Peter and Sivadasan, Naveen and Skutella, Martin},
  title =	{{Online Scheduling with Bounded Migration}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.22},
  URN =		{urn:nbn:de:0030-drops-707},
  doi =		{10.4230/DagSemProc.05031.22},
  annote =	{Keywords: scheduling, sensitivity analysis, online algorithm}
}
Document
DOI: 10.4230/DagSemProc.05031.29
Topology Matters: Smoothed Competitiveness of Metrical Task Systems

Authors: Guido Schäfer and Naveen Sivadasan

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
We consider online problems that can be modeled as metrical task systems: An online algorithm resides in a graph of n nodes and may move in this graph at a cost equal to the distance. The algorithm has to service a sequence of tasks that arrive over time; each task specifies for each node a request cost that is incurred if the algorithm services the task in this particular node. The objective is to minimize the total request plus travel cost. Borodin, Linial and Saks gave a deterministic work function algorithm (WFA) for metrical task systems having a tight competitive ratio of 2n-1. We present a smoothed competitive analysis of WFA. Given an adversarial task sequence, we add some random noise to the request costs and analyze the competitive ratio of WFA on the perturbed sequence. We prove upper and matching lower bounds. Our analysis reveals that the smoothed competitive ratio of WFA is much better than its (worst case) competitive ratio and that it depends on several topological parameters of the graph underlying the metric, such as maximum degree, diameter, etc. For example, already for moderate perturbations, the smoothed competitive ratio of WFA is O(log(n)) on a clique and O(\sqrt{n}) on a line. We also provide the first average case analysis of WFA. For a large class of probability distributions, we prove that WFA has O(log(D)) expected competitive ratio, where D is the maximum degree of the underlying graph.
Cite as

Guido Schäfer and Naveen Sivadasan. Topology Matters: Smoothed Competitiveness of Metrical Task Systems. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{schafer_et_al:DagSemProc.05031.29,
  author =	{Sch\"{a}fer, Guido and Sivadasan, Naveen},
  title =	{{Topology Matters: Smoothed Competitiveness of Metrical Task Systems}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.29},
  URN =		{urn:nbn:de:0030-drops-684},
  doi =		{10.4230/DagSemProc.05031.29},
  annote =	{Keywords: online algorithm, metrical task systems, work function algorithm, smoothed competitive analysis}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact